#include<stdio.h>
#include<stddef.h>
#define HeapMaxSize 1000

typedef int HeapType ;
typedef int (*Compare)(HeapType a, HeapType b);
typedef struct heap
{
    HeapType data[HeapMaxSize];
    size_t size;
    Compare cmp;
}Heap;

int Less(HeapType a, HeapType b){
    return a > b;
}

void HeapInit(Heap * heap, Compare compare){
    if(heap==NULL || compare == NULL){
        return;
    }
    heap->size = 0;
    heap->cmp = compare;
}

void Swap(HeapType * a , HeapType * b){
    HeapType temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

void AdjustUp(HeapType data[],size_t size, Compare cmp, ssize_t index){
    if(index >= size){
        return;
    }
    size_t child = index;
    size_t parent = (child - 1) / 2;
    while ( child > 0)
    {
        if(cmp(data[child],data[parent])){
            Swap(&data[child],&data[parent]);
        }else{
            break;
        }
        child = parent;
        parent = (child -1)/2; 
    }
    
}

void HeapInsert(Heap * heap, HeapType value){
    if(heap == NULL){
        return;
    }
    if(heap->size >= HeapMaxSize){
        return;
    }
    heap->data[heap->size++] = value;
    AdjustUp(heap->data,heap->size,heap->cmp,heap->size -1);
}

int HeapRoot(Heap * heap , HeapType * value){
    if(heap == NULL){
        return 0;
    }
    *value = heap->data[0];
    return *value;
}

void AdjustDown(HeapType data[],size_t size,Compare cmp,size_t index){
    size_t parent = index;
    size_t child = parent * 2 + 1;
    while (child < size)
    {
        if(child + 1 < size && cmp(data[child + 1],data[child])){
            child++;
        }
        if(cmp(data[child],data[parent])){
            Swap(&data[child],&data[parent]);
        }else{
            break;
        }
        parent = child;
        child = parent * 2 + 1;
    }
    
}

void HeapErase(Heap * heap){

    if(heap == NULL){
        return;
    }
    if(heap->size == 0){
        return;
    }

    Swap(&heap->data[0],&heap->data[heap->size -1]);
    --heap->size;
    AdjustDown(heap->data,heap->size,heap->cmp,0);
    
}

int HeapEmpty(Heap * heap){
    if(heap == NULL){
        return 0;
    }
    return heap->size == 0 ? 1 : 0;
}

size_t HeapSize(Heap * heap){
    if(heap == NULL){
        return 0;
    }
    return heap->size;
}

void HeapDestroy(Heap * heap){
    if(heap == NULL){
        return;
    }
    heap->size = 0;
}

void HeapSort1(HeapType data[], size_t size){
    Heap heap;
    HeapInit(&heap,Less);
    size_t i = 0; 
    for(; i < size; ++i){
        HeapInsert(&heap, data[i]);
    }

    size_t j = 0;
    while (HeapEmpty(&heap)!=1)
    {
        HeapType root = 0;
        HeapRoot(&heap,&root);
        data[j] = root;
        ++j;
        HeapErase(&heap);
    }
    
}

void HeapSort2(HeapType data[],size_t size,Compare cmp){

    if(size == 0 || size == 1){
        return;
    }

    size_t i = 0;
    for(; i < size;){
        AdjustUp(data,i,cmp,i);
        ++i;
    }

    while (i > 0)
    {
        Swap(&data[0],&data[i-1]);
        --i;
        AdjustDown(data,i,cmp,0);
    }
}

void HeapPrint(Heap * heap){
    
    for(size_t i = 0; i < heap->size; ++i){
        printf("[%d] ",heap->data[i]);
    }
    printf("\n");
}

void TestInit(){
    printf("TestInit Start\n");
    Heap heap;
    HeapInit(&heap, Less);
    printf("heap's size = %d\n",heap.size);
    printf("TestInit End\n");
}

void TestInsert(){
    printf("TestInsert Start\n");
    Heap heap;
    HeapInit(&heap,Less);
    HeapInsert(&heap,20);
    HeapInsert(&heap,21);
    HeapInsert(&heap,12);
    HeapInsert(&heap,22);
    HeapInsert(&heap,50);
    HeapInsert(&heap,40);
    HeapInsert(&heap,30);
    HeapPrint(&heap);
    printf("TestInsert End\n");
}


void TestSrot(){
    printf("TestSort Start\n");
    int array[] = {2,3,4,1,5,7};
    int length = 6;
    HeapSort1(array,length);
    // HeapSort2(array,6,Less);
    for(int i = 0; i < length; ++i){
        printf("%d ",array[i]);
    }
    printf("\n");
    printf("TestSort End\n");
}
int main(){
    // TestInit();
    // TestInsert();
    TestSrot();
    

}
